package subject_set.offer100;

/**
 * @author haomin
 * @date 2022/10/13 21:20
 **/
public class Offer10_Ⅱ {
    class Solution {
        public int numWays(int n) {
            if(n == 0) return 1;
            if(n < 3) return n;
            int[] dp = new int[n+1];
            dp[1] = 1; dp[2] = 2;
            for(int i = 3; i <= n; ++i){
                dp[i] = (dp[i-1] + dp[i-2]) % 1000000007;
            }
            return dp[n];
        }
    }
}